Section: New Results

Enumeration of metabolic stories

In many cases, we are interested in understanding how metabolism reacts when an organism is submitted to some environmental stress, that is, to establish which metabolic processes are involved in an organism's adaptation to such stress. In order to do it, elements of the metabolism such as metabolites are monitored to determine which are over- or under-produced during the stress response as compared to the organism's state in normal conditions. Such quantitative and qualitative measurements are called metabolomics. The affected part may represent only a small portion of the network, that is, involve a small subset of metabolites. The aim then is to identify subnetworks that enable to link together all elements in this subset. More formally, given such subset and a metabolic network represented as a digraph where nodes are metabolites and edges link two metabolites when one is the input of a reaction that produces the other, we are interested in identifying all maximal directed acyclic graphs that cover all the metabolites in the subset of interest, and have no sources or targets that are not one of these metabolites. Such maximal DAGs are called metabolic stories. We established already that finding one metabolic story is easy (paper submitted) and used the algorithm developed, Gobbolino (see the Softwares Section), for practical purposes (second publication in preparation). This work was done in collaboration with P. Crescenzi, A. Marchetti-Spaccamela, L. Stougie, A. Marino, F. Jourdan, and L. Cottret.